// 1-based
template <typename T, typename _Compare = std::less<T> >
class BinaryHeap
{
public:
        BinaryHeap()
        {
                clear();
        }
        T top() const
        {
                if (!empty())
                {
                        return tree[1];
                }
                else
                {
                        //throw std::logic_error("Empty Heap");
                        return tree[1];
                }
        }
        void pop()
        {
                if (!empty())
                {
                        swap(tree[1], tree[size()]);
                        tree.pop_back();
                        if (!empty())
                        {
                                siftDown(1);
                        }
                }
        }
        void push(const T &val)
        {
                tree.push_back(val);
                siftUp(tree.size() - 1);
        }
        int size() const
        {
                return tree.size() - 1;
        }
        bool empty() const
        {
                return size() == 0;
        }
        void clear()
        {
                tree.resize(1);
        }
        void updateValueAt(int idx, const T &newValue)
        {
                if (comp(newValue, tree[idx]))
                {
                        tree[idx] = newValue;
                        siftUp(idx);
                }
                else
                {
                        tree[idx] = newValue;
                        siftDown(idx);
                }
        }
        // other will NOT be modified, 2 heaps merged into this heap
        void merge(BinaryHeap &other)
        {
                unsigned int oldsize = size();
                tree.resize(1 + size() + other.size());
                copy(other.tree.begin() + 1, other.tree.end(), tree.begin() + oldsize + 1);

                for (int idx = size() / 2; idx >= 1; idx--)
                {
                        siftDown(idx);
                }
        }
private:
        void siftUp(int idx)
        {
                while (idx != 1)
                {
                        if (comp(tree[idx], tree[idx / 2]))
                        {
                                swap(tree[idx], tree[idx / 2]);
                        }
                        idx /= 2;
                }
        }
        void siftDown(int idx)
        {
                int midx = idx;
                if (2 * idx <= size() && comp(tree[2 * idx], tree[midx]))
                        midx = 2 * idx;
                if (2 * idx + 1 <= size() && comp(tree[2 * idx + 1], tree[midx]))
                        midx = 2 * idx + 1;
                if (midx != idx)
                {
                        swap(tree[idx], tree[midx]);
                        siftDown(midx);
                }
        }

private:
        vector<T> tree;
        _Compare comp;
};
